package leetcode_周赛._2023._05;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 * 第 344 场周赛
 * <p>AC_3</p>
 *
 * @author yezh
 * @date 2023/5/8 14:02
 */
public class _07 {

    /**
     * <p>找出不同元素数目差数组</p>
     * <p>算法: 前缀和</p>
     */
    public int[] distinctDifferenceArray(int[] nums) {
        int n = nums.length, cnt = 0;
        int[] ans = new int[n];
        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < n; i++) {
            if (!set.contains(nums[i])) {
                ++cnt;
                set.add(nums[i]);
            }
            ans[i] = cnt;
        }
        cnt = 0;
        set.clear();
        for (int i = n - 1; i >= 0; i--) {
            ans[i] -= cnt;
            if (!set.contains(nums[i])) {
                ++cnt;
                set.add(nums[i]);
            }
        }
        return ans;
    }

    /**
     * <p>频率跟踪器</p>
     * <p>算法: 哈希表</p>
     */
    class FrequencyTracker {
        // cnt - 每个数的出现次数; freq - 出现次数的出现次数
        private Map<Integer, Integer> cnt, freq;

        public FrequencyTracker() {
            cnt = new HashMap<>();
            freq = new HashMap<>();
        }

        public void add(int number) {
            int num = cnt.merge(number, 1, Integer::sum);
            freq.merge(num, 1, Integer::sum);
            --num;
            if (num > 0) freq.merge(num, -1, Integer::sum);
        }

        public void deleteOne(int number) {
            if (cnt.containsKey(number)) {
                int num = cnt.merge(number, -1, Integer::sum);
                freq.merge(num + 1, -1, Integer::sum);
                if (num == 0) cnt.remove(number);
                else freq.merge(num, 1, Integer::sum);
            }
        }

        public boolean hasFrequency(int frequency) {
            return freq.getOrDefault(frequency, 0) > 0;
        }
    }

    /**
     * <p>有相同颜色的相邻元素</p>
     * <p>算法: 模拟</p>
     */
    public int[] colorTheArray(int n, int[][] queries) {
        int q = queries.length, cnt = 0;
        int[] ans = new int[q], nums = new int[n + 2];
        for (int i = 0; i < q; i++) {
            int idx = queries[i][0] + 1;
            if (nums[idx] != 0) cnt -= (nums[idx] == nums[idx - 1] ? 1 : 0) + (nums[idx] == nums[idx + 1] ? 1 : 0);
            nums[idx] = queries[i][1];
            cnt += (nums[idx] == nums[idx - 1] ? 1 : 0) + (nums[idx] == nums[idx + 1] ? 1 : 0);
            ans[i] = cnt;
        }
        return ans;
    }

    /**
     * <p>使二叉树所有路径值相等的最小代价</p>
     * <p>算法: 二叉树</p>
     */
    public int minIncrements(int n, int[] cost) {
        // 1、根到两个互为兄弟叶子节点的两条路径中, 只有叶子节点的值不一样, 所以需要修改某个叶子节点的值, 使得两个叶子节点的值一样
        // 2、根到两个互为兄弟非叶子节点的两条路径中, 只有两个兄弟节点的值不一样, 所以需要修改某个兄弟节点的值
        // 3、所以把路径和从叶子节点往上传, 每传一次, 相当于把两个叶子节点去掉, 这样非叶子节点就变成叶子节点了
        int ans = 0;
        // 从最后一个非叶节点开始算
        for (int i = n / 2 - 1; i >= 0; i--) {
            // 两个子节点变成一样的
            ans += Math.abs(cost[i * 2 + 1] - cost[i * 2 + 2]);
            // 累加路径和
            cost[i] += Math.max(cost[i * 2 + 1], cost[i * 2 + 2]);
        }
        return ans;
    }

}
